package leetcode_100;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *TrappingRainWater_42 积水问题 
 *describe:用动态规划 或栈 AC 50%
 *2018年12月25日 下午3:20:30
 */
public class TrappingRainWater_42 {

	public static void main(String[] args) {
		TrappingRainWater_42 test=new TrappingRainWater_42();
		System.out.println(test.trap(new int[] {0,1,0,2,1,0,1,3,2,1,2,1}));

	}

	/**
	 * describe:双指针
	 * 2018年12月25日 下午3:20:08
	 */
	public  int trap(int[] height) {
		int left = 0, right = height.length- 1;
	    int ans = 0;
	    int left_max = 0, right_max = 0;
	    while (left < right) {
	        if (height[left] < height[right]) {
	            if(height[left] >= left_max)
	            	left_max = height[left];
	            else
	            	ans += (left_max - height[left]);
	            ++left;
	        }
	        else {
	            if(height[right] >= right_max)
	            	 right_max = height[right];
	            else
	            	ans += (right_max - height[right]);
	            --right;
	        }
	    }
	    return ans;
    }
	
	/**
	 * describe:动态规划 找左积水和右积水重叠的区域 AC 57%
	 * 2018年12月25日 下午3:05:08
	 */
	public  int trap2(int[] height) {
        int res=0;
        int left[]=new int[height.length+2];
        int right[]=new int[height.length+2];
        for(int i=1;i<=height.length;++i) {
        	left[i]=Math.max(left[i-1], height[i-1]);
        }
        for(int i=height.length;i>0;--i) {
        	right[i]=Math.max(right[i+1], height[i-1]);
        	res+=Math.min(left[i], right[i])-height[i-1];
        }
        return res;
    }
	
	
	/**
	 * describe: 超时 但结果是正确的
	 * 2018年5月15日 下午2:10:14 
	 */
	public static int trap1(int[] height) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<height.length;++i) {
        	for(int j=height[i];j>0;--j) {//开始从上往下找积水高度
        		if(map.containsKey(j)) {
        			res+=i-map.get(j)-1;
        			map.put(j, i);
        		}
        		else
        			map.put(j, i);
        	}
        }
        return res;
    }

}
